\documentclass{sig-alternate_tighter}
\usepackage{float}

\begin{document}

\title{Automobile Traffic Ecosystems within an M2M Framework}
\subtitle{}
\numberofauthors{6}
\author{
\alignauthor
Chung-Hsiang Hsueh\\
	   \affaddr{Taiwan Evolutionary Intelligence Lab}\\
       \affaddr{Department of Electrical Engineering}\\
	   \affaddr{National Taiwan University}\\
       \email{r99921044@ntu.edu.tw}
% 2nd. author
\alignauthor 
Todd McKenzie\\
	   \affaddr{iAgents Lab}\\
       \affaddr{Dept. of Computer Science and Information Engineering}\\
	   \affaddr{National Taiwan University}\\
       \email{toddmck@gmail.com} \\       
% 3rd. author
\alignauthor
Wen-Huang Lin\\
       \affaddr{Department of Electrical Engineering}\\
       \affaddr{National Taiwan University}\\
       \email{sportsbenpp@gmail.com}\\
\and
% 4th. author
\alignauthor
Fan-gang Chou\\
       \affaddr{Department of Electrical Engineering}\\
       \affaddr{National Taiwan University}\\
       \email{birdfan8814@gmail.com}\\
% 5th. author
\alignauthor
Yen-Kuang Chen\\
       \affaddr{Intel-NTU Connected Context Computing Center}\\
       \affaddr{National Taiwan University}\\
       \email{ykchen@cc.ee.ntu.edu.tw}\\
}
\maketitle

\keywords{m2m, machine to machine, internet of things, traffic, ant colony optimization, car colony optimization}

\section{Introduction}
In nature, many animal species have developed their own specialized method of communication and cooperation, such as the swarming of bees, the use of pheromones by ants, and the flashing displays of fireflies. The advance and ubiquity of smart and computationally powerful devices with in conjunction with high connectivity of such artifacts can be thought of as a slow migration toward the kinds of communication and cooperation readily found in nature. Indeed, the evolution of the machine-to-machine (M2M) framework is akin to the birth of a new species.

Applications of M2M networks are growing rapidly. One of the many such areas of application include traffic ecosystems. Within this paradigm, vehicle-to-vehicle (V2V) communication and cooperation is an important issue in M2M. When a car traverses a given path, say from A to B, at the time the car arrives at its destination we can learn a lot of information about that path from the car itself without any user interaction. Most obviously, we know exactly the route taken between points A and B. Perhaps more importantly, however, we can also infer the traffic conditions encountered along that path.


%<<<<<<< .mine
%The traffic jams in major cities of most countries have become a vital problem. For example, the Ministry of Land Infrastructure and Transport of Japan estimates the economic loss caused by traffic jam in Japan is about 100 billion US dollars per year. Today many cars are equipped with navigation systems, yet they are unable to communicate between each other. We can imagine a future where inter-navigation system %communication is commonplace, where a type of car crowd-sourcing could pave the path to more efficient transportation.
%=======
%The traffic jams in major cities in every developed country have become a big social problem. For example, Ministry of Lan Infrastructure and Transport of Japan estimates that economic loss caused by traffic jam in Japan every year is about 100 billion US dollars. Futhermore, it is not only a social wastes issue but also a big issue of saving time and the consumption of fossil fuels which may even worth many lives. So it is one of motivations for us to do this research and also take some realistic implementing problems into account. Today many cars are equipped with navigation systems, yet they are unable to communicate between each other. We can imagine a future where inter-navigation system communication is commonplace, where a type of car crowd-sourcing could pave the path to more efficient transportation.
%=======
The traffic jams in major cities in every developed country have become a big social problem. For example, Ministry of Land Infrastructure and Transport of Japan estimates that economic losses caused by traffic jams in Japan every year are about 100 billion US dollars. Furthermore, it is not only a social issue, but rather points to the larger issue of saving time and the consumption of fossil fuels. These issues provide amble motivation to perform research in this area and tackle some realistic implementation issues. Today many cars are equipped with navigation systems, yet they are unable to communicate between each other. We can imagine a future where inter-navigation system communication is commonplace, where a type of car crowd-sourcing could pave the path to more efficient transportation.



In summary, the main contributions of this paper are as follows.

\begin{itemize}
\item We propose a novel algorithm that adopts the concepts of  pheromone and utilizes it to achieve indirect communication among cars
\item We present a simulator for testing the efficiency of our algorithm
\item We design a scheme that is a possible approach for deployment within a M2M framework
\end{itemize}

In the next section, some related works are described and compared with our idea. Section \ref{SEC_REL} introduces our system that provides a feasible solution for deployment. The main idea of this work, Car Colony Optimization, is presented in section \ref{SEC_CCO}. In section \ref{SEC_SIM}, a grid-based city model is proposed to test the algorithm, and some experimental results are provided to verify our ideas. A brief conclusion and some ideas about the future works are in section \ref{SEC_CON}.

\section{Related works}
\label{SEC_REL}
Evenly redistribution of traffic resources automatically has been studied since the end of 20th centre. Dr. Dorigo first proposed Ant System in his doctoral thesis\cite{Dorigo1992} and the concepts of Ant System was quickly adopted in communication technology. M. Dorigo and G. Di Caro further proposed an innovative algorithm called AntNet in 1997 to solve the bandwidth problem in communication systems\cite{DiCaro1998}. As the amount of mobile devices grows exponentially, Benjamin Barán and Rubén Sosa studied the incorporation of AntNet and some protocols in their work\cite{Baran2001}. Due to the similarity between communicational and traffic problems, Sim and Sun studied the development of applying Ant Colony Optimization to routing and load balancing problems in their work\cite{Sim2003}. Compared to these works, we propose a novel system that builds on existing technologies and infrastructures. Within an machine-to-machine framework, our algorithm, Car Colony Optimization, is a feasible solution for traffic problems.

\section{System Scheme}
\label{SEC_SYSSCHEME}
To build a Vehicle-to-Infrastructure network, our system incorporates latest technologies on car, widely spread sensors, and specific communication protocols. The details are shown below.
\subsection{Scheme Description}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/scheme_description.pdf}
\caption{Scheme Description}
\label{scheme_description}
\end{figure}

The system scheme is depicted in Figure \ref{scheme_description}. To measure the traffic on a road, we need two parameters, the average car velocity and the density of cars on the road. Thus, we need every car to send their own velocity information to the nearest traffic light, which captured via an OBD II (On-Board Diagnostic) system which is standard equipment on most new cars. The traffic light node will perform the average velocity calculation. Moreover, we will have a camera on our light to keep track of the car density. Every light sends its information regarding the two parameters to the cloud infrastructure. If a new car joins the city, after laying in a destination, it will query the cloud for the traffic of every route between the origin and destination, and this information can be easily updated en-route as the user will pass by traffic lights periodically.

\subsection{Sensors}
We require two kinds of sensors to accomplish this task. First, OBD II(On-Board Diagnostic systems), which is a standard system keeping track of various car readings like velocity or oil consumption, and comes factory installed. This interface will enable the capture of the velocity information as required by the M2M traffic system. Second, we need a camera on every traffic light to handle the density issue. Neither sensor is expensive to deploy and neither will cause any energy issues as both the light and the car have sufficient power supply. In the event that the distance between traffic lights is large, road-side units can be placed between lights for added coverage.

\subsection{Communication} 
 
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/DSRC_protocol.pdf}
\caption{DSRC protocol}
\label{DSRC_protocol}
\end{figure} 

For communication, we use 5.9GHz DSRC (Dedicated Short Ranged Communication) based on IEEE 802.11p. This protocol is a specific standard for communication on the road. We use its V2R(vehicle to road) mode (the protocol also supports another mode called V2V [Vehicle to Vehicle]). It can communicate within a range of 300 to 1000m, and supports a data transfer rate of about 3 to 27Mbps. The V2R mode allows unidirectional broadcast and bidirectional communication. Either Non-IP base mode (handling mainly data about traffic information or real-time communication) or IPv6 mode (dealing with entertainment information on car or nearby) can be used. We utilize the Non-IP base mode for our scheme.

\section{Car Colony Optimization}
\label{SEC_CCO}
In this work, we proposed a novel method, Car Colony Optimization (CCO), which is inspired by Ant Colony Optimization\cite{Gottlieb2003} (ACO) to deal with the distribution of traffic resources adopting the concept of pheromone as in ACO. Within ACO theory, pheromones are utilized to achieve indirect communication among mobile agents in the system. The major difference between ACO and CCO is the objective function. ACO is aimed at finding a globally shortest path among all possible solutions while the focus of CCO is to evenly distribute traffic flow utilizing all possible routes within the context of minimizing travel time.

\subsection{Transition Probability Between Vertices}
In CCO, each possible road in the route is formulated as a vertex in the routing graph.  Mobile agents receive real-time information when approaching the road-side unit at the intersection and decide which direction to proceed according to the transition probability $p_t(r,s)$ between vertex $r$ and $s$.

\[
  p_t(r,s) = \left\{ 
  \begin{array}{c l}
    \dfrac{\dfrac{1}{\tau(r,s)}\eta(r,s)^\beta}{\displaystyle\sum\limits_{u\in J_k(r)}\dfrac{1}{\tau(r,u)}\eta(r,u)^\beta} & \quad \text{if $s \in J_k(r)$}\\
    0 & \quad \text{otherwise}\\
  \end{array} \right.
\]

\noindent where $\tau(r,s)$ represents the pheromone between $r$ and $s$, $\eta(r,s)$ is the inverse of the length of road $s$ times the average speed of the cars with the same direction on $s$ (e.g. $\eta(r,s) = v(r,s)/d(r,s)$), and $J_k(r)$ is the set of all possible routes.

The pheromone update function is given by
$$\tau(r,s)_t \leftarrow (1-\alpha)  \tau(r,s)_{t-1} + \vartriangle\tau(r,s)_t$$
\noindent where $\alpha$ is called the evaporation rate of pheromone.

The transition scheme is illustrated in Figure \ref{CCO_update_pheromone}.
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/CCO_pheromone.pdf}
\caption{Pheromone Update and Transition Scheme of CCO}
\label{CCO_update_pheromone}
\end{figure}

\subsection{Routing Scheme}
The routing problem is defined as finding the best path between the origin and destination points, which we illustrate in Figure \ref{CCO_routing_problem}. To find the set of candidate routes, the routing problem can be decomposed as in Figure \ref{expanded_routing_problem}.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/routingProblem.pdf}
\caption{A Typical Routing Problem}
\label{CCO_routing_problem}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/routingProblemExpanded.pdf}
\caption{The Routing Problem of CCO}
\label{expanded_routing_problem}
\end{figure}

In CCO, each car has its own pair of start and end points and the score of each path can be calculated by summing the transition probabilities along that path. For example the score of a route that passes $r_{p1}$, $r_{p2}$..., and $r_{pn}$ is given by
$$\delta_{sr_{p1}r_{p2}...r{pn_1}} = p_t(s,r_{p1})+p_t(r_{p1},r_{p2})+...+p_t(r_{pn-1},r_{pn})$$

To evenly distribute the traffic flow in the system, the path of car $k$ is chosen by sampling the routing probability,
$$p_k(route_i) = \dfrac{\delta_i}{\displaystyle\sum_{j=0}^P\delta_j}$$
where $P$ is the number of possible routes.

Mobile agents in the system can determine their own routes according to the traffic information provided by the infrastructures. The efficiency of this algorithm is shown by simulation in the next section.

\section{Simulation}
\label{SEC_SIM}
The scope of the simulation, depicted in Figure \ref{simulation_scope}, is limited to vehicle-to-infrastructure (V2I), while another available paradigms include vehicle-to-vehicle (V2V) and vehicle-to-vehicle-to-infrastructure (V2V2I). In other words, our system can be thought of as a device-to-cloud system which is an important category of M2M systems.

\begin{figure}[H]
\centering
\includegraphics[scale=0.15]{img/scope.png}
\caption{Simulation Scope}
\label{simulation_scope}
\end{figure}

The size and design of the city grid used within the simulation is as pictured in Figure \ref{grid}. In particular, the city includes twelve latitudinal and longitudinal roads and hence 144 intersections. Cars may only navigate on roads and must obey traffic rules.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/grid.png}
\caption{Simulation Environment: 12x12 Manhattan Grid}
\label{grid}
\end{figure}

Within the simulation environment, all roads consist of one lane in each direction as shown in Figure \ref{driving}. When a vehicle approaches an intersection, there are three choices of the next position, namely the appropriate lane associated with maintaining a straight course as well as both turning left and turning right. We restrict all cars in the environment to obey traffic rules. That is, cars wait at red lights, queuing up behind other cars as necessary. Also, we assume that there are no traffic accidents which occur during the simulation. We do, however, investigate a case where there is an a-prior vehicle accident which occupies a large area of the grid which vehicles must circumnavigate.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/driving.png}
\caption{City Navigation Fundamentals}
\label{driving}
\end{figure}

The geometry of the city and automobile motion are defined as in Figure \ref{geometry}. Each street in the city is exactly three car-lengths long and at each time step in the simulation cars may move one car-length assuming the road in front of the car is open or becomes open via the motion of other cars in that time step.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/geometry.png}
\caption{City Grid Geometry and Vehicular Motion}
\label{geometry}
\end{figure}

\subsection{Experimental Results}

In this simulation, randomly places cars and randomly establish destinations within the city in a uniform fashion. The results in Figure \ref{traffic_random} reveal that the addition of the M2M does not lead to a decrease in the travel time as desired. The reason for this is obvious, however. As the traffic is randomly distributed in the city, making navigation decisions with and without the additional information of uniform traffic are very similar.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/traffic_random.png}
\caption{Random Traffic Simulation Results}
\label{traffic_random}
\end{figure}

Next, we explore the case where rush hour is present in the city. All cars are placed in one quadrant of the city and are assigned destinations inthe opposite quadrant of the city. Without M2M, a bottleneck forms where all cars try to move greedily to their destinations. With the addition of M2M, cars become aware of traffic in along their path from their origin to destination and thus are more readily able to circumnavigate traffic and hence reduce overall travel time as shown in Figure \ref{traffic_rush}.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/traffic_rush.png}
\caption{Rush Hour Traffic Simulation Results}
\label{traffic_rush}
\end{figure}

Finally, a large accident occurs in the city where the center-most intersections of the city are blocked. We still consider a rush hour condition, thus cars must drive around the accident area to arrive at their destination. This creates an even greater bottleneck in the city and thus the benefit of the M2M system, as depicted in Figure \ref{traffic_rush_accident}, is even more evident in this scenario.

\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{img/traffic_rush_accident.png}
\caption{Rush Hour Traffic with Accident Simulation Results}
\label{traffic_rush_accident}
\end{figure}

\section{Conclusions}
\label{SEC_CON}
The results of our research underscore the potential benefits of the application of an M2M framework to the automobile traffic ecosystem. We found that the advantage of the system was realized only in the cases where the traffic within the city was non-uniform. This makes sense as when the traffic is roughly similar in different areas of the city, the knowledge that all areas are clear or congested is of little value. Luckily traffic, in general, is time dependent and non-uniform. This means that our finding of travel time savings of up to 40\% in our simulation is a significant figure and motivates future research in this area. A possible area of future work is the addition of vehicle-to-vehicle (V2V) communication, adding robustness in the case of an infrastructure failure due to a nature disaster, for example. Another direction would be to take the drivers preferences into account. Overall, it is very promising that M2M systems will be important in the smart city of the future, within which M2M-based traffic systems will play a vital role.

\bibliographystyle{abbrv}
\bibliography{m2m_finalproject_team8}
\end{document}
